package com.ywk.base.dataStructure.binarytree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HuffmanTreeDemo {

	public static void main(String[] args) {
		int[] arr= {1,3,6,7,8,13,29};
		HuffmanNode root=creatHuffmanTree(arr);
		preOrder(root);
	}
	
	public static HuffmanNode creatHuffmanTree(int[] arr) {
		List<HuffmanNode> nodes=new ArrayList<HuffmanNode>();
		for(int value: arr) {
			nodes.add(new HuffmanNode(value));
		}
		while(nodes.size()>1) {
			Collections.sort(nodes);//集合排序Collections.sort();数组排序Arrays.sort()
			//System.out.println(nodes);
			HuffmanNode leftNode=nodes.get(0);
			HuffmanNode rightNode=nodes.get(1);
			HuffmanNode parent=new HuffmanNode(leftNode.getValue()+rightNode.getValue());
			parent.left=leftNode;
			parent.right=rightNode;
			nodes.remove(leftNode);
			nodes.remove(rightNode);
			nodes.add(parent);
		}
		return nodes.get(0);
	}
	
	public static void preOrder(HuffmanNode root){
		if(root!=null) {
			root.preOrder();
		}else {
			System.out.println("空树");
		}
	}
}
class HuffmanNode implements Comparable<HuffmanNode>{
	private int value;
	public HuffmanNode left;
	public HuffmanNode right;
	
	public HuffmanNode(int value) {
		super();
		this.value = value;
	}
	
	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}
	
	//前序遍历
	public void preOrder() {
		System.out.println(this);
		if(this.left!=null) {
			this.left.preOrder();
		}
		if(this.right!=null) {
			this.right.preOrder();
		}
	}
	
	@Override
	public String toString() {
		return "HuffmanNode [value=" + value + "]";
	}

	@Override
	public int compareTo(HuffmanNode o) {
		return this.value-o.value;//表示从小到大排序
	}
	
}